home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / reduce.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  6.9 KB  |  250 lines  |  [TEXT/R*ch]
  1. /*
  2.     module: reduce.c
  3.     purpose: Perform the Espresso-II reduction step
  4.  
  5.     Reduction is a technique used to explore larger regions of the
  6.     optimization space.  We replace each cube of F with a smaller
  7.     cube while still maintaining a cover of the same logic function.
  8. */
  9.  
  10. #include "espresso.h"
  11.  
  12. static bool toggle = TRUE;
  13.  
  14.  
  15. /*
  16.     reduce -- replace each cube in F with its reduction
  17.  
  18.     The reduction of a cube is the smallest cube contained in the cube
  19.     which can replace the cube in the original cover without changing
  20.     the cover.  This is equivalent to the super cube of all of the
  21.     essential points in the cube.  This can be computed directly.
  22.  
  23.     The problem is that the order in which the cubes are reduced can
  24.     greatly affect the final result.  We alternate between two ordering
  25.     strategies:
  26.  
  27.     (1) Order the cubes in ascending order of distance from the
  28.     largest cube breaking ties by ordering cubes of equal distance
  29.     in descending order of size (sort_reduce)
  30.  
  31.     (2) Order the cubes in descending order of the inner-product of
  32.     the cube and the column sums (mini_sort)
  33.  
  34.     The real workhorse of this section is the routine SCCC which is
  35.     used to find the Smallest Cube Containing the Complement of a cover.
  36.     Reduction as proposed by Espresso-II takes a cube and computes its
  37.     maximal reduction as the intersection between the cube and the
  38.     smallest cube containing the complement of (F u D - {c}) cofactored
  39.     against c.
  40.  
  41.     As usual, the unate-recursive paradigm is used to compute SCCC.
  42.     The SCCC of a unate cover is trivial to compute, and thus we perform
  43.     Shannon Cofactor expansion attempting to drive the cover to be unate
  44.     as fast as possible.
  45. */
  46.  
  47. pcover reduce(F, D)
  48. INOUT pcover F;
  49. IN pcover D;
  50. {
  51.     register pcube last, p, cunder, *FD;
  52.  
  53.     /* Order the cubes */
  54.     if (use_random_order)
  55.     F = random_order(F);
  56.     else {
  57.     F = toggle ? sort_reduce(F) : mini_sort(F, descend);
  58.     toggle = ! toggle;
  59.     }
  60.  
  61.     /* Try to reduce each cube */
  62.     FD = cube2list(F, D);
  63.     foreach_set(F, last, p) {
  64.     cunder = reduce_cube(FD, p);        /* reduce the cube */
  65.     if (setp_equal(cunder, p)) {            /* see if it actually did */
  66.         SET(p, ACTIVE);    /* cube remains active */
  67.         SET(p, PRIME);    /* cube remains prime ? */
  68.     } else {
  69.         if (debug & REDUCE) {
  70.         printf("REDUCE: %s to %s %s\n",
  71.             pc1(p), pc2(cunder), print_time(ptime()));
  72.         }
  73.         set_copy(p, cunder);                /* save reduced version */
  74.         RESET(p, PRIME);                    /* cube is no longer prime */
  75.         if (setp_empty(cunder))
  76.         RESET(p, ACTIVE);               /* if null, kill the cube */
  77.         else
  78.         SET(p, ACTIVE);                 /* cube is active */
  79.     }
  80.     free_cube(cunder);
  81.     }
  82.     free_cubelist(FD);
  83.  
  84.     /* Delete any cubes of F which reduced to the empty cube */
  85.     return sf_inactive(F);
  86. }
  87.  
  88. /* reduce_cube -- find the maximal reduction of a cube */
  89. pcube reduce_cube(FD, p)
  90. IN pcube *FD, p;
  91. {
  92.     pcube cunder;
  93.  
  94.     cunder = sccc(cofactor(FD, p));
  95.     return set_and(cunder, cunder, p);
  96. }
  97.  
  98.  
  99. /* sccc -- find Smallest Cube Containing the Complement of a cover */
  100. pcube sccc(T)
  101. INOUT pcube *T;         /* T will be disposed of */
  102. {
  103.     pcube r;
  104.     register pcube cl, cr;
  105.     register int best;
  106.     static int sccc_level = 0;
  107.  
  108.     if (debug & REDUCE1) {
  109.     debug_print(T, "SCCC", sccc_level++);
  110.     }
  111.  
  112.     if (sccc_special_cases(T, &r) == MAYBE) {
  113.     cl = new_cube();
  114.     cr = new_cube();
  115.     best = binate_split_select(T, cl, cr, REDUCE1);
  116.     r = sccc_merge(sccc(scofactor(T, cl, best)),
  117.                sccc(scofactor(T, cr, best)), cl, cr);
  118.     free_cubelist(T);
  119.     }
  120.  
  121.     if (debug & REDUCE1)
  122.     printf("SCCC[%d]: result is %s\n", --sccc_level, pc1(r));
  123.     return r;
  124. }
  125.  
  126.  
  127. pcube sccc_merge(left, right, cl, cr)
  128. INOUT register pcube left, right;       /* will be disposed of ... */
  129. INOUT register pcube cl, cr;            /* will be disposed of ... */
  130. {
  131.     INLINEset_and(left, left, cl);
  132.     INLINEset_and(right, right, cr);
  133.     INLINEset_or(left, left, right);
  134.     free_cube(right);
  135.     free_cube(cl);
  136.     free_cube(cr);
  137.     return left;
  138. }
  139.  
  140.  
  141. /*
  142.     sccc_cube -- find the smallest cube containing the complement of a cube
  143.  
  144.     By DeMorgan's law and the fact that the smallest cube containing a
  145.     cover is the "or" of the positional cubes, it is simple to see that
  146.     the SCCC is the universe if the cube has more than two active
  147.     variables.  If there is only a single active variable, then the
  148.     SCCC is merely the bitwise complement of the cube in that
  149.     variable.  A last special case is no active variables, in which
  150.     case the SCCC is empty.
  151.  
  152.     This is "anded" with the incoming cube result.
  153. */
  154. pcube sccc_cube(result, p)
  155. register pcube result, p;
  156. {
  157.     register pcube temp=cube.temp[0], mask;
  158.     int var;
  159.  
  160.     if ((var = cactive(p)) >= 0) {
  161.     mask = cube.var_mask[var];
  162.     INLINEset_xor(temp, p, mask);
  163.     INLINEset_and(result, result, temp);
  164.     }
  165.     return result;
  166. }
  167.  
  168. /*
  169.  *   sccc_special_cases -- check the special cases for sccc
  170.  */
  171.  
  172. bool sccc_special_cases(T, result)
  173. INOUT pcube *T;                 /* will be disposed if answer is determined */
  174. OUT pcube *result;              /* returned only if answer determined */
  175. {
  176.     register pcube *T1, p, temp = cube.temp[1], ceil, cof = T[0];
  177.     pcube *A, *B;
  178.  
  179.     /* empty cover => complement is universe => SCCC is universe */
  180.     if (T[2] == NULL) {
  181.     *result = set_save(cube.fullset);
  182.     free_cubelist(T);
  183.     return TRUE;
  184.     }
  185.  
  186.     /* row of 1's => complement is empty => SCCC is empty */
  187.     for(T1 = T+2; (p = *T1++) != NULL; ) {
  188.     if (full_row(p, cof)) {
  189.         *result = new_cube();
  190.         free_cubelist(T);
  191.         return TRUE;
  192.     }
  193.     }
  194.  
  195.     /* Collect column counts, determine unate variables, etc. */
  196.     massive_count(T);
  197.  
  198.     /* If cover is unate (or single cube), apply simple rules to find SCCCU */
  199.     if (cdata.vars_unate == cdata.vars_active || T[3] == NULL) {
  200.     *result = set_save(cube.fullset);
  201.     for(T1 = T+2; (p = *T1++) != NULL; ) {
  202.         (void) sccc_cube(*result, set_or(temp, p, cof));
  203.     }
  204.     free_cubelist(T);
  205.     return TRUE;
  206.     }
  207.  
  208.     /* Check for column of 0's (which can be easily factored( */
  209.     ceil = set_save(cof);
  210.     for(T1 = T+2; (p = *T1++) != NULL; ) {
  211.     INLINEset_or(ceil, ceil, p);
  212.     }
  213.     if (! setp_equal(ceil, cube.fullset)) {
  214.     *result = sccc_cube(set_save(cube.fullset), ceil);
  215.     if (setp_equal(*result, cube.fullset)) {
  216.         free_cube(ceil);
  217.     } else {
  218.         *result = sccc_merge(sccc(cofactor(T,ceil)),
  219.              set_save(cube.fullset), ceil, *result);
  220.     }
  221.     free_cubelist(T);
  222.     return TRUE;
  223.     }
  224.     free_cube(ceil);
  225.  
  226.     /* Single active column at this point => tautology => SCCC is empty */
  227.     if (cdata.vars_active == 1) {
  228.     *result = new_cube();
  229.     free_cubelist(T);
  230.     return TRUE;
  231.     }
  232.  
  233.     /* Check for components */
  234.     if (cdata.var_zeros[cdata.best] < CUBELISTSIZE(T)/2) {
  235.     if (cubelist_partition(T, &A, &B, debug & REDUCE1) == 0) {
  236.         return MAYBE;
  237.     } else {
  238.         free_cubelist(T);
  239.         *result = sccc(A);
  240.         ceil = sccc(B);
  241.         (void) set_and(*result, *result, ceil);
  242.         set_free(ceil);
  243.         return TRUE;
  244.     }
  245.     }
  246.  
  247.     /* Not much we can do about it */
  248.     return MAYBE;
  249. }
  250.